#include <stdio.h>
#include <stdlib.h>

#define STACK_MAX_SIZE	30
#define QUEUE_MAX_SIZE	30

#ifndef elemType
	typedef char elemType;
#endif


struct btree_node
{
	char data;	// elemType data;
	struct btree_node *left;
	struct btree_node *right;
};

void init_btree(struct btree_node **bt)
{
	*bt = NULL;
}

void create_btree(struct btree_node **bt, char *a)
{
	struct btree_node *p;
	struct btree_node *s[STACK_MAX_SIZE];
	int top = 1;
	int k;
	int i = 0;
	*bt = NULL;

	while (a[i] != '\0') {
		switch(a[i]) {
			case ' ':
				break;
			case '(':
				if (top == STACK_MAX_SIZE -1) {
					printf("stack space too litte\n");
					exit(1);
				}
				top++;
				s[top] = p;
				k = 1;
				break;
			case ')':
				if (top == -1) {
					printf("¶þ²æÊ÷¹ãÒå±í×Ö·ûŽ®ŽíÎó!n");
					exit(1);
				}
				top--;
				break;
			case ',':
				k = 2;
				break;
			default:
				p = malloc(sizeof(struct btree_node));
				p->data = a[i];
				p->left = p->right = NULL;
				if (*bt == NULL) {
					*bt = p;
				}
				else {
					if (k == 1) 
						s[top]->left = p;					
					else
						s[top]->right = p;
				}
		}
		i++;
	}
}

int empty_btree(struct btree_node *bt)
{
	if (bt == NULL)
		return 1;
	else
		return 0;
}

int btree_depth(struct btree_node *bt)
{
	int dep1, dep2;

	dep1 = dep2 = 0;

	if (bt == NULL)
		return 0;
	else {
		dep1 = btree_depth(bt->left);
		dep2 = btree_depth(bt->right);

		if (dep1 > dep2) 
			return dep1 + 1;
		else
			return dep2 + 1;
	}
}

char *find_btree(struct btree_node *bt, char x)
{
	char *p = NULL;

	if (bt == NULL)
		return NULL;
	else {
		if (bt->data = x)
			return &(bt->data);
		else {
			if (p = find_btree(bt->left, x)) 
				return p;			
			if (p = find_btree(bt->right, x))
				return p;
		}

		return NULL;
	}
}

/* non recursion find */
char *find_btree_non(struct btree_node *bt, char x)
{
	while (bt != NULL) {
		if (x == bt->data)
			return &(bt->data);
		else if (x < bt->data)
			bt = bt->left;
		else
			bt = bt->right;
	}
}

void insert_btree(struct btree_node *bt, char x)
{
	struct btree_node *p;

	if (bt == NULL) {
		p = (struct btree_node)malloc(sizeof(struct btree_node));
		p->data = x;
		p->left = p->right = NULL;
		*bt = p;
	}
	else if (x < (*bt)->data)
		insert_btree(&((*bt)->left), x);
	else
		insert_btree(&((*bt)->right), x);
}

/* non recursion insert */
void insert_btree_non(struct btree_node **bt, char x)
{
	struct btree_node *p;
	struct btree_node *t = *bst, *parent = NULL;

	while (t != NULL) {
		parent = t;
		if (x < t->data)
			t = t->left;
		else 
			t = t->right;
	}

	p = (struct btree_node)malloc(sizeof(struct btree_node));
	p->data = x;
	p->left = p->right = NULL;
	if (parent == NULL)
		*bt = p;
	else if (x < parent->data)
		parent->left = p;
	else
		parent->right = p;
}

void print_btree(struct btree_node *bt)
{
	if (bt != NULL) 
		printf("%c", bt->data);
	if (bt->left != NULL || bt->right != NULL) {
		printf("(");
		print_btree(bt->left);
		if (bt->right != NULL)
			printf(",");
		print_btree(bt->right);
		printf(")");
	}
}

void clear_btree(struct btree_node **bt)
{
	if (*bt != NULL) {
		clear_btree(&((*bt)->left));
		clear_btree(&((*bt)->right));
		free(*bt);
		*bt = NULL;
	}
}

int delete_btree(struct btree_node **bt, char x)
{
	struct btree_node *temp = *bt;
	struct btree_node *p1, *p2;

	if (*bt == NULL)
		return 0;
	if (x < (*bt)->data)
		return delete_btree(&((*bt)->left), x);
	if (x > (*bt)->data)
		return delete_btree(&((*bt)->right), x);

	if ((*bt)->left == NULL) {
		*bt = (*bt)->right;
		free(temp);
		return 1;
	}

	if ((*bt)->right == NULL) {
		*bt = (*bt)->left;
		free(temp);
		return 1;
	}
	else {
		if ((*bt)->left->right == NULL) {
			(*bt)-data = (*bt)->left->data;
			return delete_btree(&((*bt)->left), (*bt)->data);
		}
		else {
			p1 = *bt;
			p2 = p1->left;
			while (p2->right != NULL) {
				p1 = p2;
				p2 = p2->right;
			}
			(*bt)->data = p2->data;
			return delete_btree(&(p1->right), p2->data);
		}
	}
}

/* forword */
void pre_order(struct btree_node *bt)
{
	if (bt != NULL) {
		printf("%c", bt->data);
		pre_order(bt->left);
		pre_order(bt->right);
	}
}

/* middle */
void mid_order(struct btree_node *bt)
{
	if (bt != NULL) {
		mid_order(bt->left);
		printf("%c", bt->data);
		mid_order(bt->right);
	}
}

/* back */
void post_order(struct btree_node *bt)
{
	if (bt != NULL) {
		post_order(bt->left);
		post_order(bt->right);
		printf("%c", bt->data);
	}
}

void level_order(struct btree_node *bt)
{
	struct btree_node *p;
	struct btree_node *q[QUEUE_MAX_SIZE];
	int front = 0, rear = 0;

	if (bt != NULL) {
		rear = (rear + 1) % QUEUE_MAX_SIZE;
		q[rear] = bt;
	}

	while (front != rear) {
		front = (front + 1) % QUEUE_MAX_SIZE;
		p = q[front];
		printf("%c", p->data);

		if (p->left != NULL) {
			rear = (rear + 1) % QUEUE_MAX_SIZE;
			q[rear] = p->left;
		}

		if (p->right != NULL) {
			rear = (rear + 1) % QUEUE_MAX_SIZE;
			q[rear] = p->right;
		}
	}
}



int main()
{
	struct btree_node *bt, *pt;
	char *b;
	char x, *px;
	
	init_btree(&bt); 
	b = "a(b(c), d(e(f, g), h(, i)))";
	create_btree(&bt, b);
//printf("b ==== %s\n", b);
	//if (bt != NULL);
		//printf("%c", bt->data);
	 printf("output : ");
	 print_btree(bt);   
	 printf("n");
	 
	 printf("forword : ");  
	 pre_order(bt);
	 printf("n");
	 printf("middle  : ");  
	 mid_order(bt);
	 printf("n");
	 printf("back    : ");  
	 post_order(bt);
	 printf("n");
	 printf("level   : ");  
	 level_order(bt);
	 printf("n");

	 printf("input a char for find : ");
	 scanf(" %c", &x);  
	 px = find_btree(bt, x);
	 if(px){
		 printf("find success", *px);
	 }else{
		 printf("find unsuccess");
	 }

	 printf("depth   : ");
	 printf("%dn", btree_depth(bt));
	 clear_btree(&bt);
